//
// Created by daiyizheng on 2022/4/12.
//
#include <iostream>
using namespace std;
//判断字串是否是回文
bool isPalindrome(string s){
    int i = 0;
    int j = s.length()-1;
    while (i<j){
        if(s[i]!=s[j])return false;
        i++;
        j--;
    }
    return true;
}
int countSubstrings(string s) {
    if(s.length()==0)return 0;
    int res = 0;

    //穷举所有字串
    for (int i = 0; i < s.length(); ++i) {
        for (int j = i; j < s.length(); ++j) {
            string sub = s.substr(i, j-i+1);
            if(isPalindrome(sub))res++;
        }
    }
    return res;
}

//动态规划
#include <vector>
int countSubstrings1(string s) {
    if(s.length()==0)return 0;
    int n = s.length();
    //定义状态数组
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int res = 0;

    //初始化， 对角线为true
    for (int i = 0; i < n; ++i) {
        dp[i][i] = true;
        res++;
    }
    //状态转移,先控制列
    for (int j = 1; j < n ; j++) {//列
        for (int i = 0; i < j; i++) {//行, 不等于
            //【i，j】
            bool  isCharEqual = s[i]==s[j];
            if(j-i==1){
                dp[i][j] = isCharEqual;
            }else if(!isCharEqual){
                dp[i][j] = false;
            }else{
                dp[i][j] = dp[i+1][j-1];
            }
            if(dp[i][j])res++;
        }
    }
    return res;
}